#!/usr/bin/env python3
# coding: utf-8

from __future__ import print_function, division, unicode_literals
import itertools
import copy


class TreeNode(object):
    """tree node"""

    def __init__(self):
        self.edges = dict()


def another_gift_new1(items, gifts):
    """hello, my name is johnny"""
    def dfs_populate_tree(troot, gift):
        """fill the tree with gift sets"""
        if gift == []:
            return 0
        swap_elem = len(gift) - 1
        while gift[0] in troot.edges:
            assert swap_elem > 0, "cannot build tree..?"
            gift[0], gift[swap_elem] = gift[swap_elem], gift[0]
            swap_elem -= 1
        edge = gift.pop(0)
        troot.edges[edge] = TreeNode()
        gift.sort()
        return dfs_populate_tree(troot.edges[edge], gift)

    def make_new_gift(tree, items):
        """hello, my name is roger"""
        if type(items) != type(list()):
            items = sorted(list(items))
        return 0

    gifts_list = [sorted(list(x)) for x in gifts]
    tree = TreeNode()
    for gift in gifts_list:
        try:
            dfs_populate_tree(tree, copy.deepcopy(gift))
        except:
            print('nope')
            return None
    return make_new_gift(tree, items)


def another_gift(items, gifts):
    # FIXME: work out the solution
    # 'items' has 'n' elements
    for k in range(1, len(items) + 1):                        # 1
        for newgift in itertools.combinations(items, k):      # 2 ** n
            for gift in gifts:                                # len(gifts)
                if frozenset(newgift).issubset(gift) or \
                        frozenset(newgift).issuperset(gift):  # 2*n*set_seek(gift)
                    break
            else:
                return frozenset(newgift)
    return None
    # total complexity: O(2 ** n * len(gifts) * n * set_seek(n))

if __name__ == "__main__":
    #another_gift = another_gift_new1
    print(another_gift(frozenset([1, 2, 3, 4]),
                       [frozenset([1, 2]), frozenset([2, 3, 4])]))
    print(another_gift(frozenset([1, 2, 3]), [frozenset([1, 2]),
                                              frozenset([3])]))

    print(another_gift(frozenset([1, 2, 3, 4]),
                       [frozenset([1, 2]), frozenset([2, 3, 4]),
                        frozenset([1])]))
    print(another_gift(frozenset([1, 2, 3, 4]),
                       [frozenset([1, 2]), frozenset([2, 3, 4]),
                        frozenset([2])]))
    print(another_gift(frozenset([1, 2, 3, 4]),
                       [frozenset([1, 2]), frozenset([2, 3, 4]),
                        frozenset([3])]))
    print(another_gift(frozenset([1, 2, 3, 4]),
                       [frozenset([1, 2]), frozenset([2, 3, 4]),
                        frozenset([4])]))

    print(another_gift(frozenset([1, 2, 3, 4]),
                       [frozenset([1, 2]), frozenset([2, 3, 4]),
                        frozenset((1, 3))]))
    print(another_gift(frozenset([1, 2, 3, 4]),
                       [frozenset([1, 2]), frozenset([2, 3, 4]),
                        frozenset([3]), frozenset((1, 3))]))

    print(another_gift(frozenset([1, 2, 3, 4]),
                       [frozenset([1, 2]), frozenset([2, 3, 4]),
                        frozenset((1, 3)), frozenset((1, 4))]))
    print(another_gift(frozenset([1, 2, 3, 4]),
                       [frozenset([1, 2]), frozenset([2, 3, 4]),
                        frozenset([3]), frozenset((1, 3)),
                        frozenset((1, 4))]))
